package Demo2;


import java.util.Stack;

import static java.io.ObjectInputFilter.merge;

public class Sort {
    //默认从小到大排序
    public static void insertSort(int[] arr){
        //直接插入排序
        //时间复杂度：最好情况：数据完全有序，O（n） 最坏情况：数据完全逆序，O（n^2)
        //结论：当给的数据越有序排序越快
        //如果有一组基本有序的数据要排序————》这个快
        //空间复杂度：O（1）
        //稳定性：稳定的排序
        //一个本身稳定的排序 是可以实现为不稳定的
        //但是相反 一个本身就不稳定的排序 是不可能实现为稳定的
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i-1;
            for (; j >= 0; j--) {
                if(arr[j] > tmp){
                    //如果大于就换位
                    arr[j+1] = arr[j];
                }else{
                    //不大于就放回去，并且跳出循环
                   // arr[j+1] = tmp;
                    break;
                }
            }
            arr[j+1] = tmp;
        }
    }
    //希尔排序
    //采用分组：每组进行插入排序     跳跃式的分组可能会将更小的元素 尽可能地往前放
    //时间复杂度：？？？n^1.3~n^1.5
    //空间：O(1)
    //稳定性:不稳定
    public  static void shellSort(int[] arr){
        int gap = arr.length;
        while(gap > 1){
            gap /= 2;
            shell(arr,gap);
        }
    }
    private  static  void shell(int[] arr,int gap){
        for (int i = gap; i < arr.length; i++) {
            //最后都会看成一组进行排序所以++/+gap不影响
            int tmp = arr[i];
            int j = i-gap;
            for (; j >= 0; j-=gap) {
                if(arr[j] > tmp){
                    //如果大于就换位
                    arr[j+gap] = arr[j];
                }else{
                    //不大于就放回去，并且跳出循环
                    // arr[j+1] = tmp;
                    break;
                }
            }
            arr[j+gap] = tmp;
        }
    }
    //直接选择排序
    //[j]<[minIndex]——>更新
    //时间复杂度：不管最好最坏   都是O(n^2)
    //空间复杂度：O(1)
    //稳定性：不稳定
    public static  void selectSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            int j = i+1;
            for (; j < arr.length; j++) {
               if (arr[j] < arr[minIndex]){
                   minIndex = j;
               }
            }
           swap(arr,minIndex,i);
        }
    }
    private static void swap(int[] arr,int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    public static void selectSort2(int[] arr){
        int left = 0;
        int right = arr.length-1;
        while(left < right){
            int minIndex = left;
            int maxIndex = left;
            for (int i = left+1; i <= right ; i++) {
                //更新最大最小值下标
                if(arr[i] < arr[minIndex]){
                    minIndex = i;
                }
                if(arr[i] > arr[maxIndex]){
                    maxIndex = i;
                }
            }
            swap(arr,left,minIndex);
            //最大值正好在最小值地的位置交换到了minIndex
            if(maxIndex == left){
                maxIndex = minIndex;
            }
            swap(arr,right,maxIndex);
            left++;
            right--;
        }
    }
    //堆排序
    //时间复杂度：O（n*logN）
    //空间复杂度：O（1）
    //稳定性：不稳定的
    //数据量大的时候堆排一定比希尔快
    public static void heapSort(int[] arr){
        creatBigHeap(arr);
        int end = arr.length-1;
        while(end > 0) {
            swap(arr, 0, end);
            shiftDown(arr, 0, end);
            end--;
        }
    }
    private static void creatBigHeap(int[] arr){
        for (int parent = (arr.length-1-1)/2;parent >= 0 ; parent--) {
            shiftDown(arr,parent,arr.length);
        }
    }

    private static void shiftDown(int[]arr,int parent,int end) {
        int child = 2*parent+1;
        while(child < end){
            if(child + 1 < end && arr[child] < arr[child+1]){
                child++;
            }
            if(arr[child] > arr[parent]){
                swap(arr,child,parent);
                parent = child;
                child = 2*parent+1;
            }else{
                break;
            }
        }
    }
    //冒泡排序
    //时间复杂度：O(n^2)  如果加了优化  最好情况O（n）
    //空间复杂度：O(1)
    //稳定性：稳定
    public  static void bubleSort(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {//比较的趟数
            boolean flg = false;
            for (int j = 0; j < arr.length-1-i; j++) {
                //每次比较都比上一次少一次
                if(arr[j] > arr[j+1]){
                    swap(arr,j,j+1);
                    flg = true;
                }
            }
            if(!flg){
                return;
            }
        }
    }
    //快速排序
    //时间复杂度：最好情况：完全二叉树 O(N*logN)              最坏情况：O(N^2)单分支
    //空间复杂度：最好情况：完全二叉树 O(logN)  最坏情况：O(N)单分支
    //稳定性：不稳定
    //优化方法：三数取中法降低树的高度      小的有序的区间用插入排序    减少递归次数
    //1、挖坑法     2、hor法      3、前后指针法
    public static void quickSort(int[] arr){
        quick(arr,0,arr.length-1);
    }
    private static void quick(int[] arr,int start,int end){
        if(start >= end) return;//左边是一个节点 或者 一个节点也没有了
        if(end-start+1 <= 15){
        //插入排序
            insertSortRange(arr,start,end);
            return;
        }

        //三数取中
        int index =  midOfTree(arr,start,end);
        swap(arr,index,start);//此时交换完之后  一定能保证start下标是中间大的数字
        System.out.println("start:"+start+" "+"end"+end);
        //取基准
        int priot = parttion(arr,start,end);
        //类比遍历二叉树
        quick(arr,start,priot-1);
        quick(arr,priot+1,end);
    }

    private static int midOfTree(int[] arr, int left, int right) {
        int mid = (left+right)/2;
        if(arr[left] < arr[right]){
            if(arr[mid] < arr[left]){
                return left;
            } else if(arr[mid] > arr[right]){
                return right;
            } else{
                return mid;
            }
        }else {
                if(arr[mid] > arr[left]){
                    return left;
                } else if (arr[mid] < arr[right]) {
                    return right;
                }else {
                    return mid;
                }
        }

    }
    private static void insertSortRange(int[] arr,int begin,int end){
        for (int i = begin+1; i <= end; i++) {
            int tmp = arr[i];
            int j = i-1;
            for (; j >= begin; j--) {
                if(arr[j] > tmp){
                    //如果大于就换位
                    arr[j+1] = arr[j];
                }else{
                    //不大于就放回去，并且跳出循环
                    // arr[j+1] = tmp;
                    break;
                }
            }
            arr[j+1] = tmp;
        }
    }

    private static int parttionHoare(int[] arr,int left,int right){
        int k = arr[left];
        int i = left;
        while(left < right){
            //如果left先走的话，left和right相遇的地方一定是比k大的
            while(left < right && arr[right] >= k){//这里为什么取等
                //如果不取可能会死循环
                right--;
            }//right    下标一定是比k小的数据
            while(left < right && arr[left] <= k){//这里为什么取等
                left++;
            }//left     下标一定是比k大的数据
            swap(arr,left,right);
        }
        //相遇的位置和i交换
        swap(arr, left, i);
        return left;
    }
    //挖坑法(建议使用)
    private static int parttion(int[] arr,int left,int right){
        int k = arr[left];
        int i = left;
        while(left < right){
            //如果left先走的话，left和right相遇的地方一定是比k大的
            while(left < right && arr[right] >= k){//这里为什么取等
                //如果不取可能会死循环
                right--;
            }//right    下标一定是比k小的数据
            arr[left] = arr[right];
            while(left < right && arr[left] <= k){//这里为什么取等
                left++;
            }//left     下标一定是比k大的数据
            arr[right] = arr[left];
        }
        //相遇的位置和i交换
        arr[left] = k;
        return left;
    }
    //前后指针法
    private static int partition(int[] array, int left, int right) {
        int prev = left ;
        int cur = left+1;
        while (cur <= right) {
            if(array[cur] < array[left] && array[++prev] != array[cur]) {
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,left);
        return prev;
    }
    //非递归实现快排
    public static  void quickSortNor(int[] arr){
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = arr.length-1;
        int piovt = partition(arr,left,right);
        if(piovt-1 > left){//说明左边一定有两个元素
            stack.push(left);
            stack.push(piovt-1);
        }
        if(piovt+1 < right){//说明右边一定有两个元素
            stack.push(piovt+1);
            stack.push(right);
        }
        while(!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
             piovt = partition(arr,left,right);
            if(piovt-1 > left){//说明左边一定有两个元素
                stack.push(left);
                stack.push(piovt-1);
            }
            if(piovt+1 < right){//说明右边一定有两个元素
                stack.push(piovt+1);
                stack.push(right);
            }
        }
    }
    //归并排序  分解左边 分解右边 合并
    //最常用的外部排序
    //空间复杂度：O（n）
    //时间复杂度：不管有无序都是 N*logN
    //稳定的排序：插入  冒泡  归并
    public static void mergeSort(int[] arr){
        mergrSortFunc(arr,0,arr.length-1);
    }
    private static void mergrSortFunc(int[] arr,int left,int right){
        if(left >= right) return;;
        int mid = (left+right)/2;
        //分解左边
        mergrSortFunc(arr,left,mid);
        //分解右边
        mergrSortFunc(arr,mid+1,right);
        //合并
        merge(arr,left,right,mid);
    }

    private static void merge(int[] arr, int left, int right, int mid) {
        int s1 = left;
        int s2 = mid+1;
        int[] tmpArr = new int[right-left+1];
        int k = 0;
        //证明两个区间    都同时有数据的
        while(s1 <= mid && s2<= right){
            if(arr[s1] <= arr[s2]){
                tmpArr[k++] = arr[s1++];
            }else{
                tmpArr[k++] = arr[s2++];
            }
        }
        //把剩余的元素放入tmpArr中
        while(s1 <= mid){
            tmpArr[k++] = arr[s1++];
        }
        while(s2 <= right){
            tmpArr[k++] = arr[s2++];
        }
        //tmpArr   里面一定是有序的
        for (int i = 0; i < tmpArr.length; i++) {
            arr[i+left] = tmpArr[i];
        }
    }
    //非递归实现归并
    public static void mergeSort2(int[] arr){
        int gap = 1;
        while(gap < arr.length){
            for (int i = 0; i < arr.length; i += 2*gap) {
                int left = i;
                int mid = left+gap-1;
                int right = mid+gap;
                if(mid >= arr.length){
                    mid = arr.length-1;
                } if(right>= arr.length){
                    right = arr.length-1;
                }
                merge(arr,left,right,mid);
            }
            gap *= 2;
        }
    }
    //计数排序
    //时间复杂度：O（n+范围）
    //空间复杂度：O(n+范围）
    //计数排序的时间与范围有关
    //稳定
    public static void countSort(int[] arr){
        int minVal = arr[0];
        int maxVal = arr[0];
        //1、求当前数组的最大值  和  最大值
        for (int i = 1; i < arr.length; i++) {
            if(arr[i] < minVal){
                minVal = arr[i];
            }
            if(arr[i] > maxVal){
                maxVal = arr[i];
            }
        }
        //2、跟进最大值 和 最小值 来确定数组大小
        int[] count = new int[maxVal - minVal+1];
        //3、遍历原来数组开始计数
        for (int i = 0; i < arr.length; i++) {
            count[arr[i] - minVal]++;
        }
        //4、遍历计数count把当前元素写回arr
        int index = 0;//重新表示arr数组的下标
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0){
                arr[index] = i+minVal;
                index++;
                count[i]--;
            }
        }
    }
}   
